#include <stdio.h>
// #define NDEBUG
#include <assert.h>

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// void swap(SElemType *a,SElemType *b){
//     SElemType tmp = *a;
//     *a = *b;
//     *b = tmp;
// }

// // 相比插入排序多了动态步长
// void shell_sort(SElemType arr[], int len){
//     int gap = len/2;  // 间隔--步长
//     SElemType choose;     // 可以认为是选中，要进行插入的牌
//     int preIndex; // 选中的牌的前一个位置（开始进行插入的）
//     // 动态步长
//     while (gap > 0){
//         printf("gap: %d\r\n", gap);
//         // 注意这里还是要i++
//         for (int i=gap; i<len; i++){
//             choose = arr[i];
//             preIndex = i-gap;
//             while(preIndex >=0 && arr[preIndex] > choose){
//                 arr[preIndex+gap] = arr[preIndex];
//                 preIndex -= gap;
//             }
//             arr[preIndex+gap] = choose;
//         }
//         gap = gap/2;
//     }
// }

// 相比插入排序多了动态步长
void shell_sort(SElemType arr[], int len){
    int gap;  // 间隔--步长
    SElemType choose;     // 可以认为是选中，要进行插入的牌
    int preIndex; // 选中的牌的前一个位置（开始进行插入的）

    // 动态步长
    for(gap = len/2; gap>0 ; gap = gap/2){
        printf("gap: %d\r\n", gap);
        // 注意这里还是要i++
        for (int i=gap; i<len; i++){
            choose = arr[i];
            for(preIndex = i-gap; preIndex >=0 && arr[preIndex] > choose; preIndex -= gap){
                arr[preIndex+gap] = arr[preIndex];
            }
            arr[preIndex+gap] = choose;
        }
    }
}



int main(){
    SElemType arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    shell_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
            printf("%d ", arr[i]);
    return 0;
}
